package data_struct

import "fmt"

//数据结构 线性表 单链表 实现

//链表节点
type MyNode struct {
	X    interface{}
	next *MyNode
}

//链表
type MyList struct {
	Head   *MyNode
	length int
}

func MakeList() *MyList {
	list := MyList{
		Head: &MyNode{X: 0},
	}
	return &list
}

//判空
func (t *MyList) IsEmpty() bool {
	return t.Head.next == nil
}

//链表长度
func (t *MyList) Length() int {
	return t.length
}

//清空； 将链表每一个节点都置空、（如果直接将第一个节点置空如何？由GC回收？）
func (t *MyList) Clear() {
	current := t.Head.next
	for current != nil {
		temp := current.next
		current = nil
		current = temp
	}
	t.Head.next = nil
}

//插入部
func (t *MyList) InsertHead(node *MyNode) bool {
	current := t.Head        //记录之前的第一个节点
	node.next = current.next //将之前的节点，归到新节点的指针区
	current.next = node      //将新节点更新到最开始
	t.length++
	return true
}

//插入尾部
func (t *MyList) InsertTail(node *MyNode) bool {
	//找到最后一个节点
	current := t.Head
	for current.next != nil {
		current = current.next
	}
	current.next = node
	t.length++
	return true
}

//插入。 插入i位置 ，则 i-1的节点next指现elem, elem的next指向之前i-1节点的next
func (t *MyList) Insert(i int, elem MyNode) bool {
	if i < 0 || i > t.length {
		return false
	}
	current := t.Head
	for k := 0; k < i; k++ {
		//找到需要插入的位置
		current = current.next
	}
	elem.next = current.next //将后边的链，放到的elem
	current.next = &elem     //将elem，插入到前一个节点的next，完成锁链
	t.length++
	return true
}

//删除节点。 找到目标节点的上一个节点，找到指针，将其指针重定向目标节点的下一个节点
func (t *MyList) Delete(i int) (r interface{}, ok bool) {
	if i < 0 || i >= t.length {
		return
	}
	current := t.Head
	var before *MyNode

	for k := 0; k <= i; k++ {
		//找到需要插入的位置的前一个节点
		before, current = current, current.next
	}
	before.next = current.next //将current空中
	r = current.X
	current = nil
	t.length--
	return r, true
}

//获取指定位序的节点的值
func (t *MyList) GetElem(index int) (r MyNode, ok bool) {
	if index < 0 || index >= t.length {
		return
	}
	current := t.Head

	for k := 0; k <= index; k++ {
		//找到需要插入的位置的前一个节点
		current = current.next
	}
	r = MyNode{X: current.X}
	return r, true
}

//找到第一个节点的值是x,返回其位序 0 表示未找到
func (t *MyList) GetIndex(x interface{}) (i int) {
	for current := t.Head; current.next != nil; {
		current = current.next
		if current.X == x {
			break
		}
		i++
	}
	return
}

//获取指定节点的前驱节点
func (t *MyList) PrevNode(node MyNode) (r MyNode, ok bool) {
	//方法一
	//index := t.GetIndex(node.X)
	//if index < 1 {
	//  return
	//}
	//return t.GetElem(index - 1)
	//方法二
	var tmpNode *MyNode
	for current := t.Head; current.next != nil; {
		tmpNode = current
		current = current.next
		if current.X == node.X {
			break
		}
	}
	if tmpNode == t.Head {
		return
	}
	return *tmpNode, true
}

//找后继
func (t *MyList) NextNode(node MyNode) (r MyNode, ok bool) {
	for current := t.Head; current.next != nil; {
		current = current.next
		if current.X == node.X {
			if current.next == nil {
				return
			}
			return *current.next, true
		}
	}
	return
}

func (list *MyList) Traverse(fn func(node interface{})) {
	current := list.Head.next
	for current != nil {
		fn(current.X)
		current = current.next
	}
}

// 打印链表信息
func (list *MyList) PrintList() {
	if list.IsEmpty() {
		fmt.Println("空链表")
		return
	}
	current := list.Head.next
	fmt.Println("链表内容:")
	i := 0
	for current != nil {
		fmt.Printf("#%d,value: -> %v \n", i, current.X)
		current = current.next
	}
}
